#leetcode 96 不同的二叉搜索树

#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(n)
#方法：动态规划

class Solution:
    def numTrees(self, n: int) -> int:
        dp=[0]*(n+1)
        dp[0]=1
        for i in range(n+1):
            for j in range(i):
                dp[i]=dp[i]+dp[j]*dp[i-j-1]
        return dp[n]

#测试数据
n=3
#预期输出：5
solution=Solution()
print(solution.numTrees(n))

n=1
#预期输出：1
solution=Solution()
print(solution.numTrees(n))
